
<!DOCTYPE html>
<html>

	<head>
	<title>CAIJL's Blog</title>
	<meta charset="utf-8"/>
	<link rel="stylesheet" href="/font-awesome-4.7.0/css/font-awesome.min.css">

	<link rel="stylesheet" href="/bootstrap-3.3.7/css/bootstrap.min.css">
	<script src="/jquery-2.1.1/jquery.min.js"></script>
	<script src="/bootstrap-3.3.7/js/bootstrap.min.js"></script>

	<link rel="stylesheet" href="/css/bootstrap-slider.min.css">
	<script src="/js/bootstrap-slider.min.js"></script>
	
	<link rel="stylesheet" href="/css/main.css">
	<script src="/js/main.js"></script>
	
	<link rel="stylesheet" href="/css/cursor.css">
	<script src="/js/cursor.js"></script>
	
	
	<link rel="stylesheet" href="/css/code.css">
	<!--link rel="stylesheet" href="/css/markdown.css"-->
	
	<link rel="stylesheet" href="/css/head.css">

	<script src="/js/window.js"></script>
	<script src='//unpkg.com/valine/dist/Valine.min.js'></script>
	</head>
<body>

	<link rel="stylesheet" href="/katex/katex.min.css" crossorigin="anonymous">
	<script src="/katex/katex.min.js" crossorigin="anonymous"></script>
	<script src="/katex/contrib/mathtex-script-type.min.js" defer></script>
	<script defer src="/katex/contrib/auto-render.min.js"crossorigin="anonymous"
	    onload="renderMathInElement(document.body);"></script>
	<script>document.addEventListener("DOMContentLoaded", function() {renderMathInElement(document.body,{"delimiters":[{left: "$", right: "$", display: false}]});});</script>
	<nav class="navbar navbar-default header card" role="navigation" style="width: 100%;">
	<div class="container-fluid"> 
	<div class="navbar-header">
		<button type="button" class="navbar-toggle" data-toggle="collapse"
				data-target="#example-navbar-collapse">
			<span class="icon-bar"></span>
			<span class="icon-bar"></span>
			<span class="icon-bar"></span>
		</button>
		<a class="navbar-brand" href="/"><span><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="bold">C</mi><mi mathvariant="bold">A</mi><mi mathvariant="bold">I</mi><mi mathvariant="bold">J</mi><msup><mi mathvariant="bold">L</mi><mo mathvariant="bold" lspace="0em" rspace="0em">′</mo></msup><mi mathvariant="bold">s</mi><mi mathvariant="bold">B</mi><mi mathvariant="bold">L</mi><mi mathvariant="bold">O</mi><mi mathvariant="bold">G</mi></mrow><annotation encoding="application/x-tex">\mathbf{CAIJL'sBLOG}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height: 0.751892em; vertical-align: 0em;"></span><span class="mord"><span class="mord mathbf">C</span><span class="mord mathbf">A</span><span class="mord mathbf">I</span><span class="mord mathbf">J</span><span class="mord"><span class="mord mathbf">L</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height: 0.751892em;"><span class="" style="top: -3.063em; margin-right: 0.05em;"><span class="pstrut" style="height: 2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathbf mtight">′</span></span></span></span></span></span></span></span></span><span class="mord mathbf">s</span><span class="mord mathbf">B</span><span class="mord mathbf">L</span><span class="mord mathbf">O</span><span class="mord mathbf">G</span></span></span></span></span></span></a>
	</div>
	<div class="collapse navbar-collapse" id="example-navbar-collapse">
		<ul class="nav navbar-nav" style="background-color:#fcfcfc">
			<li><a href="/"><i class="menu-item-icon fa fa-fw fa-home"></i>首页</a></li>
			<li><a href="/archives/"><i class="menu-item-icon fa fa-fw fa-archive"></i>文章</a></li>
			<li><a href="/tags/"><i class="menu-item-icon fa fa-fw fa-tags"></i>标签</a></li>
			<li><a href="/settings/"><i class="menu-item-icon fa fa-fw fa-cogs"></i>设置</a></li>
			<!--li><a href="/about/"><i class="menu-item-icon fa fa-fw fa-user"></i>关于</a></li-->
			<li><a href="/games/"><i class="menu-item-icon fa fa-fw fa-gamepad"></i>其它</a></li>
			

		</ul>
	</div>
	</div>
	</nav>
<div class="container">
	<div style="height: 60px;"></div>
	<div class="row" >
		<div class="col-md-8">
			<div class="panel panel-default card" style="padding: 10px;position: relative;">
                <img src='/img/bg/1.png' style="width:100%"/>
				<span style="position: absolute;left:15px;bottom:15px;width:90%;"><font class="view-text" style="color:#fcfcfc;font-size:25px">WC补题记录</font><br><a href="/tags/2021/" class="tag"><span  style="background-color: rgb(52, 152, 219);">2021</span></a></span>
			</div>
			<div class="panel panel-default card" style="padding: 10px;" id="main">
                <p>
<script type="math/tex">\Large\mathbb{WC}</script> 又被 <a href="https://www.luogu.com.cn/user/141179"><script type="math/tex">\rm\color{black} p\color{red}{igstd}</script></a>吊打力</p>
<!--more-->
<p>都 <script type="math/tex">\rm 1202</script> 了 <script type="math/tex">\rm WC</script> 为什么还不支持 <script type="math/tex">\rm C++11</script>
</p>
<h2 id="t1">T1.<a href="https://www.luogu.com.cn/problem/P7323">括号路径</a></h2>
<blockquote>
<p>这是l，这是r。这些边我不加（小声）【战术停顿】，这些边我不加（大声）！暴力怎么做，暴力是不是！加边！加边！加边！然后，并查集查询。</p>
</blockquote>
<p>考虑一个点 <script type="math/tex">x</script> 有 <script type="math/tex">a\to x</script> 的左括号并且有 <script type="math/tex">b\to x</script> 的 左括号，那么 <script type="math/tex">a,b</script> 必然双向可达，可以把 <script type="math/tex">a,b</script> 缩成一个点。</p>
<p>这个用并查集加边加边加边就做完了。</p>
<p>块内所有点双向可达，块间点不可达。</p>
<p>为了加进所有的边，需要一个队列。每次取队首合并的时候，如果有新的点使得成立，就把新的点加进队列。</p>
<p><a href="https://www.luogu.com.cn/record/46300858"><script type="math/tex">\color{skyblue}{\text{评测记录}}</script></a>  <a href="https://loj.ac/s/1060462"><script type="math/tex">\color{red}{\rm LOJ}</script></a></p>
<p>好像用 <script type="math/tex">\rm unordered\_map</script> + 启发式是 <script type="math/tex">\mathcal{O}(n\log n)</script> 但因为常数原因没 <script type="math/tex">\rm map</script> 的 <script type="math/tex">\mathcal{O}(n\log^2n)</script> 快</p>
<h2 id="t2">T2.<a href="https://www.luogu.com.cn/problem/P7324">表达式求值</a></h2>
<p>神仙题。无限 <script type="math/tex">\rm stO</script> 出题人</p>
<p>首先不难发现所有的位都是独立的。用<script type="math/tex">\rm dp</script> 做到<script type="math/tex"> \mathcal{O}(nm|E|)</script> 其实是不难的（虽然我考场上挂了/kel</p>
<p>复杂度瓶颈其实是那个 <script type="math/tex">n</script> ，把每一位差拆开来算其实是超级不划算的。考虑有什么办法预处理一些神必得东西可以在较短的时间内求出每一位的值。</p>
<p>这个 <script type="math/tex">m</script> 很小我们尝试指数级（不然也不会这么小）</p>
<p>首先 <script type="math/tex">10!</script> 肯定是不行的。</p>
<p>于是就是想不到的神仙操作。</p>
<p>考虑把 <script type="math/tex">10</script> 个数放进两个集合 <script type="math/tex">P</script> 与 <script type="math/tex">Q</script> 使得 <script type="math/tex">\forall i\in P,j\in Q</script> ，都有 <script type="math/tex">A_i>A_j</script>
</p>
<p>这个集合的数量显然就是 <script type="math/tex">2^m</script>
</p>
<p>建一棵表达式数，记 <script type="math/tex">dp(x,P)</script> 为节点 <script type="math/tex">x</script> 算出 <script type="math/tex">A_i(i\in P)</script> 的情况数。</p>
<p>这个东西是可以快速求出答案的，设排列后的顺序为 <script type="math/tex">p_0,p_1,p_2,\ldots</script>,答案就是 </p>
<p>
<script type="math/tex; mode=display">\sum_{i=0}A_{p_i}\left[dp(rt,\{p_0,p_1,\ldots,p_i\})-dp(rt,\{p_0,p_1,\ldots,p_{i-1}\})\right]</script>
</p>
<p>差分操作就是求恰好是 <script type="math/tex">p_i</script>
</p>
<p>想到这一步就不难 <script type="math/tex">\rm dp</script> 了，记 <script type="math/tex">sum(i)</script> 为子树 <script type="math/tex">i</script> 的方案数,<script type="math/tex">lc,rc</script> 为左右儿子</p>
<ol>
<li><code>&lt;</code> <script type="math/tex">dp(x,S)=dp(lc,S)\times dp(rc,S)</script>
</li>
<li><code>&gt;</code> <script type="math/tex">dp(x,S)=dp(lc,S)\times sum(rc)+dp(rc,S)\times(sum(lc)-dp(lc,S))</script>
</li>
<li><code>?</code> 把两种加起来就可以了。</li>
</ol>
<p><a href="https://www.luogu.com.cn/record/46311959"><script type="math/tex">\color{skyblue}{\text{评测记录}}</script></a>  <a href="https://loj.ac/s/1060733"><script type="math/tex">\color{red}{\rm LOJ}</script></a></p>
<h2 id="t3">T3.<a href="https://www.luogu.com.cn/problem/P7325">斐波那契</a></h2>
<p>
<script type="math/tex; mode=display">
\begin{cases}
F_0&=a,\\
F_1&=b,\\
F_n&=F_{n-1}+F_{n-2}
\end{cases}
\Longrightarrow
\begin{cases}
fib_0&=0,\\
fib_1&=1,\\
F_n&=bfib_{i}+afib_{i-1}
\end{cases}
</script>
</p>
<p>记 <script type="math/tex">(a,b)F_n</script> 为 <script type="math/tex">F_0=a,F_1=b</script> 的斐波那契数列的第 <script type="math/tex">n</script> 项</p>
<p>
<script type="math/tex; mode=display">(a,b)F_n\equiv0\pmod m\Longleftrightarrow (\frac{a}{\gcd(a,b,m)},\frac{b}{\gcd(a,b,m)})F_n\equiv0 \pmod{\frac{m}{\gcd(a,b,m)}}</script>
</p>
<p>记 <script type="math/tex">\frac{a}{\gcd(a,b,m)},\frac{b}{\gcd(a,b,m)},\frac{m}{\gcd(a,b,m)}</script> 分别为 <script type="math/tex">a^\prime,b^\prime,m^\prime</script> 。对于每个 <script type="math/tex">m^\prime</script> 分别处理。不难发现不同<script type="math/tex">m^\prime</script> 的数量上界为 <script type="math/tex">2\times\sqrt{m}</script> 而且几乎不可能卡满。
(打了个表只有<script type="math/tex">128</script>)</p>
<p>
<script type="math/tex; mode=display">
\begin{aligned}
&a^\prime fib_{i-1}+b^\prime fib_i\equiv 0\pmod {m^\prime}\\
&a^\prime fib_{i-1}\equiv(m^\prime-b^\prime) fib_i\pmod {m^\prime}
\end{aligned}
</script>
首先有 <script type="math/tex">a|m\Rightarrow a|(ba\bmod m)</script>
</p>
<p>感性理解为若一个数是模数的因数，那么其若干倍在膜 <script type="math/tex">m</script> 下仍是其的倍数。</p>
<p>考虑 <script type="math/tex">a' fib_{i-1}\equiv (m'-b') fib_i\pmod {m'}</script>
</p>
<p>(<script type="math/tex">\gcd(a',m'-b',m')=1,\gcd(fib_i,fib_{i-1})=1</script>)</p>
<p>
<script type="math/tex">a'fib_{i-1}\bmod m'</script> 是 <script type="math/tex">\gcd(a',m')</script> 、<script type="math/tex">\gcd(fib_{i-1},m')</script> 的倍数</p>
<p>
<script type="math/tex">(m'-b')fib_i\bmod m'</script> 是 <script type="math/tex">\gcd(m'-b',m')</script>、<script type="math/tex">\gcd(fib_i,m')</script> 的倍数</p>
<p>由于相等：</p>
<p>
<script type="math/tex">(m'-b')fib_i\bmod m'</script> 是 <script type="math/tex">\gcd(a',m')</script> 、<script type="math/tex">\gcd(fib_{i-1},m')</script> 的倍数</p>
<p>
<script type="math/tex">a'fib_{i-1}\bmod m'</script> 是 <script type="math/tex">\gcd(m'-b',m')</script>、<script type="math/tex">\gcd(fib_i,m')</script> 的倍数
<script type="math/tex; mode=display">
\begin{cases}
\gcd(a',m')|(m'-b')fib_i\\
\gcd(fib_i,m')|a'fib_{i-1}
\end{cases}
</script>
由于 <script type="math/tex">\gcd(a',m')\perp (m'-b')</script> 且 <script type="math/tex">\gcd(fib_i,m')\perp fib_{i-1}</script> ，有：
<script type="math/tex; mode=display">\begin{cases}\gcd(a',m')|fib_i\\ \gcd(fib_i,m')|a'\end{cases}
\Rightarrow \begin{cases}\gcd(a',m')|\gcd(fib_i,m')\\ \gcd(fib_i,m')|\gcd(a',m')\end{cases}</script>
</p>
<p>因而得证 <script type="math/tex">\gcd(a',m')=\gcd(fib_i,m')</script>。同理易得 <script type="math/tex">\gcd(b',m')=\gcd(fib_{i-1},m')</script>
</p>
<p>所以有：</p>
<p>
<script type="math/tex; mode=display">
\begin{cases}
\gcd(a^\prime,m^\prime)=\gcd(fib_i,m^\prime)\\
\gcd(fib_{i-1},m^\prime)=\gcd(m^\prime-b^\prime,m^\prime)\\
\frac{a^\prime}{\gcd(a^\prime,m^\prime)}\frac{fib_{i-1}}{\gcd(fib_{i-1},m^\prime)}\equiv\frac{m^\prime-b^\prime}{\gcd(m^\prime-b^\prime,m^\prime)}\frac{fib_i}{\gcd(fib_i,m^\prime)}
\color{black}\pmod {\frac{m^\prime}{\gcd(a^\prime,m^\prime)\gcd(fib_{i-1},m^\prime))}}
\end{cases}
</script>
最后一个柿子可以写成分式，记从左至右依次为 <script type="math/tex">a^{\prime\prime}</script>,<script type="math/tex">fib_{i-1}^\prime</script>,<script type="math/tex">b^{\prime\prime}</script>,<script type="math/tex">fib_i^\prime</script>,<script type="math/tex">m^{\prime\prime}</script>，则有：
<script type="math/tex; mode=display">\frac{a^{\prime\prime}}{b^{\prime\prime}}\equiv \frac{fib_i^{\prime}}{fib_{i-1}^\prime}\pmod {m^{\prime\prime}}</script>
两侧都只与自己有关，并且都在模下有意义。可以压成一个三元组，用 <code>map</code> 查询即可</p>
<p><a href="https://www.luogu.com.cn/record/46353137"><script type="math/tex">\color{skyblue}{\text{评测记录}}</script></a>  <a href="https://loj.ac/s/1061522"><script type="math/tex">\color{red}{\rm LOJ}</script></a></p>
<p>
<script type="math/tex; mode=display">\Huge\rm Goodbye\ OI</script>
</p>
			</div>
			<div class="panel panel-default card" style="padding: 10px;height: 50px;font-size: 20px;">
				<a style="float: left;" href="\article\CF701.html"><i class="fa fa-angle-double-left"></i></a><a style="float: right;" href="\article\P7325.html"><i class="fa fa-angle-double-right"></i></a>
			</div>
			<div class="panel panel-default card" style="padding: 10px;font-size: 20px;" id="vcomments">
				
			</div>
			<script>
				new Valine({
					el: '#vcomments',
					appId: 'PAlFUPg0pQVTFTEo8gCB4BCf-gzGzoHsz',
					appKey: 'U38ejnLUiizJ6vLyp6ql4hRq',
					path: window.location.pathname
				})
			</script>
		</div>
		<div class="col-md-3">
				<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-info"></i>&emsp;
						<strong>文章信息</strong>
					</h3>
				</div>
                <div style="margin: 10px;">
                    <div style="margin-top: 8px;display: flex;"> 
    <span style="flex: 1 0 auto;margin-right: 6px;">标题</span>
    <span><font style="font-weight: bold">WC补题记录</font></span>
	</div><div style="margin-top: 8px;display: flex;"> 
    <span style="flex: 1 0 auto;margin-right: 6px;">日期</span>
    <span>2021-02-14 19:48:27</span>
	</div>
                </div>
				</div>
				<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-tag"></i>&emsp;
						<strong>标签</strong>
					</h3>
				</div>
				<div style="margin: 10px;">
					<a href="/tags/2021/" class="tag"><span  style="background-color: rgb(52, 152, 219);">2021</span></a>
				</div>
				</div>
				
			<div class="panel panel-default card">
					<div class="panel-heading">
						<h3 class="panel-title">
							<i class="fa fa-user-circle-o"></i>&emsp;
							<strong>caijicjl</strong>
						</h3>
					</div>
					<div style="width: 60%;display: inline-block;padding-top: 10px;">
						<ul class="propertyLinks" style="list-style-type: none;">
							<li>
								<img style="vertical-align:middle;position:relative;top:-2px" src="/img/rating-16x16.png">
								Rating:&nbsp;
								<span style="font-weight:bold;color: gray ">312</span>
							</li>
							<li>
								<img style="vertical-align:middle;position:relative;top:-2px" src="/img/star_blue_16.png">
								Contribution:&nbsp;
								<span style="color:gray;font-weight:bold;">0</span>
							</li>
						</ul>
						<ul class="nav-links">
							<li><a href="/settings/">Settings</a></li>
							<li><a href="/archives/">Blog</a></li>
							<li><a href="/teams">Teams</a></li>
							<li><a href="/submissions/dingdingsb">Submissions</a></li>
							<li><a href="/usertalk">Talks</a></li>
							<li><a href="/contests/with/dingdingsb">Contests</a></li>
						</ul>
					</div>
					<div style="display:inline-block;vertical-align: top;margin: 10px;text-align: center;">
						<div style="height:50px;width:50px"><img src="/img/avatar.png"/></div>
						<div><a href="https://www.luogu.com.cn/user/174304" style="font-weight:bold;color:gray">caijicjl</a></div>
					</div>
				</div>
		<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-external-link"></i>&emsp;
						<strong>画中画</strong>
					</h3>
				</div>
				<div style="width:100%;margin:10px">
				<input type="text" id="url"/>
				<input value="创建" type="button" onclick="creat('kk')" /> 
				</div>
		</div>
		<script src="/js/hitokoto.js"></script>
							

				
				<span id="kk"></span>
				<div  id="myScrollspy" class="card" style="width: 100%;"  data-spy="affix">
					<script src="/js/make_toc.js"></script>
				</div>
		</div>
	</div>
 </div>
</body>
</html>
